/*
题目链接:https://leetcode.cn/problems/count-equal-and-divisible-pairs-in-an-array/description/?envType=daily-question&envId=2025-04-17
*/
//题解代码:

const int MX = 101;
vector<int> divisors[MX];

auto init = [] {
    for (int i = 1; i < MX; i++) {
        for (int j = i; j < MX; j += i) {
            divisors[j].push_back(i);//i是j的因子
        }
    }
    return 0;
}();


class Solution {
public:
    int gcd_(int x,int y){
        return x%y==0 ? y : gcd(y,x%y); 
    }

    int countPairs(vector<int>& nums, int k) {
        int ans = 0;
        int n = nums.size();
        unordered_map<int,int> ump;
        for(int j=0;j<n;++j){
            int x = nums[j];
            if(j && x==nums[0]){
                ans++;//单独统计i==0
            }
            int m = k / gcd(j,k);
            ans += ump[m<<10 | x];
            for(auto& d : divisors[j]){
                ump[d<<10 | x]++;
            }
        }
        return ans;
    }
};
